/*
* 双指针学习
*/

//移动零
//https://leetcode.cn/problems/move-zeroes/submissions/
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        //已处理区间     0区间       待处理区间
//        // [0,pos]  [pos+1,cur-1]  [cur,n-1]
//        int n = nums.size();
//        for (int cur = 0, pos = -1; cur < n; ++cur)
//            if (nums[cur])
//                swap(nums[++pos], nums[cur]);
//    }
//};


//复写零
//https://leetcode.cn/problems/duplicate-zeros/submissions/
// class Solution {
// public:
//     void duplicateZeros(vector<int>& arr) {
//         int n = arr.size();
//         //1.找到最后一个复写的位置
//         int cur = 0,pos = -1;
//         while(cur < n)
//         {
//             if(arr[cur]) ++pos;
//             else pos += 2;
//             if(pos >= n-1) break;
//             ++cur;
//         }
//         //2.判断边界条件
//         if(pos == n)
//         {
//             arr[n-1] = 0;
//             pos -= 2;
//             --cur;
//         }
//         //3.从后向前复写
//         while(pos>=0)
//         {
//             if(arr[cur]) arr[pos--] = arr[cur];
//             else
//             {
//                 arr[pos--] = 0;
//                 arr[pos--] = 0;
//             }
//             --cur;
//         }
//     }
// };


//快乐数
//https://leetcode.cn/problems/happy-number/description/
// class Solution {
// public:
//     int squareSum(int n)
//     {
//         int tmp = 0;
//         while (n)
//         {
//             tmp += (n % 10) * (n % 10);
//             n /= 10;
//         }
//         return tmp;
//     }

//     //环形链表 快慢指针问题
//     bool isHappy(int n) {
//         int slow = n;
//         int fast = n;

//         do
//         {
//             slow = squareSum(slow);
//             fast = squareSum(squareSum(fast));
//         }while (slow != fast);
//         return slow == 1 ? true : false;
//     }
// };


//盛水最多的容器
//https://leetcode.cn/problems/container-with-most-water/submissions/
// class Solution {
// public:
//     int maxArea(vector<int>& height) {
//         int left = 0,right = height.size()-1,ret = 0;

//         while(left < right)
//         {
//             //由于木桶原理 水桶的最大盛水量由短板决定
//             ret = max(ret,(right-left)*(height[left]>height[right]?height[right]:height[left]));

//             //如果一个left>right 那么right与下一个数相乘 必定没有left与另一个数相乘大
//             if(height[left]>height[right]) --right;
//             else ++left;
//         }
//         return ret;
//     }
// };


//有效三角形的个数
//https://leetcode.cn/problems/valid-triangle-number/submissions/
// class Solution {
// public:
//     int triangleNumber(vector<int>& nums) {
//         sort(nums.begin(),nums.end());
//         int ret = 0,n = nums.size();

//         //先确定最后一个最大的数(因为排序过)
//         for(int i = n-1;i>=2;--i)
//         {
//             int left = 0,right = i-1;
//             while(left < right)
//             {
//                 //如果当前的left和right满足，则中间的其他数一定满足 因为排序过
//                 if(nums[left]+nums[right] > nums[i])
//                 {
//                     ret += right-left;
//                     --right;
//                 }
//                 else ++left;
//             }
//         }
//         return ret;
//     }
// };


//查找总价格为目标值的两个商品
//https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/submissions/
// class Solution {
// public:
//     vector<int> twoSum(vector<int>& price, int target) {
//         int left = 0,right = price.size()-1;
//         while(left < right)
//         {
//             //数组是已经排序过了
//             //如果相加较小 则继续加大数字
//             if(price[left]+price[right]<target)
//                 ++left;
//             else if(price[left]+price[right]>target)
//                 --right;
//             else return {price[left],price[right]};
//         }
//         return {-1,-1};
//     }
// };


//三数之和
//https://leetcode.cn/problems/3sum/description/
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         sort(nums.begin(),nums.end());
//         vector<vector<int>> ret;
//         int n = nums.size();
//         for(int i = 0;i<n;) //确定一个数
//         {
//             int left = i+1,right = n-1;
//             while(left < right)
//             {
//                 int sum = nums[i]+nums[left]+nums[right];
//                 if(sum > 0) --right;
//                 else if(sum < 0) ++left;
//                 else
//                 {
//                     ret.push_back({nums[i],nums[left],nums[right]});
//                     ++left;
//                     --right;
//                     //去重
//                     while(left < right && nums[left-1] == nums[left]) ++left;
//                     while(left < right && nums[right+1] == nums[right]) --right;
//                 }
//             }
//             //去重
//             ++i;
//             while(i < n && nums[i-1] == nums[i]) ++i;
//         }
//         return ret;
//     }
// };


//四数之和
//https://leetcode.cn/problems/4sum/submissions/
// class Solution {
// public:
//     vector<vector<int>> fourSum(vector<int>& nums, int target) {
//         int n = nums.size();
//         vector<vector<int>> ret;
//         sort(nums.begin(),nums.end());

//         for(int i = 0;i<n;) //固定第一个数
//         {
//             //接下来就是三数之和
//             for(int k = i+1;k<n;)
//             {
//                 int left = k+1,right = n-1;
//                 //得到另外一半数之和的相反数
//                 long long sum1 = (long long)target - nums[i] - nums[k];
//                 while(left < right)
//                 {
//                     //知道其中两个数 找另外两个数
//                     long long sum2 = nums[left] + nums[right];
//                     if(sum2 > sum1) --right;
//                     else if(sum2 < sum1) ++left;
//                     else 
//                     {
//                         ret.push_back({nums[i],nums[k],nums[left++],nums[right--]});
//                         while(left < right && nums[left-1] == nums[left]) ++left;
//                         while(left < right && nums[right+1] == nums[right]) --right;
//                     }
//                 }
//                 ++k;
//                 while(k < n && nums[k-1] == nums[k]) ++k;
//             }
//             ++i;
//             while(i < n && nums[i-1] == nums[i]) ++i;
//         }
//         return ret;
//     }
// };

